iT邦幫忙

0

Leetcode 刷題日記 - 383. Ransom Note (Python)

  • 分享至 

  • xImage
  •  

前言

最近在刷 LeetCode,今天要來跟大家分享一下我解「383. Ransom Note」的過程!這題雖然標示為 Easy,解題邏輯不難,但因為對語法不熟,還是讓我卡了一下,所以想把我的解題過程記錄下來,方便未來複習檢視,也給跟我一樣正在學習的朋友們一個參考。如果大神路過有更好的建議幫助我進步歡迎在下方留言。

題目

簡單來說,就是給你兩個字串,一個是「ransomNote」(贖金信),另一個是「magazine」(雜誌)。題目要我們判斷,ransomNote 裡面的每個字母,能不能從 magazine 裡面找到對應的字母,而且每個字母只能用一次。

解題思路

一開始,我想到幾個簡單的判斷條件:

  1. 字數檢查: ransomNote 的字數不能比 magazine 多,不然一定組不出來。
  2. 字母種類檢查: ransomNote 裡面的字母,一定要是 magazine 裡面的子集。
  3. 建立字母頻率表: 使用一個 dictionary 來記錄 magazine 裡面每個字母出現的次數。
  4. 逐一檢查 ransomNote: 對於 ransomNote 中的每個字母,檢查 dictionary 裡對應的字母數量是否足夠。

解法

class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    # 檢查字數和字母種類
    if len(ransomNote) > len(magazine) or not set(ransomNote).issubset(set(magazine)):
      return False

    # 建立字母頻率表
    magz_table = dict()
    for m in magazine:
      magz_table[m] = magz_table.get(m, 0) + 1

    # 逐一檢查 ransomNote
    for r in ransomNote:
      if r not in magz_table or magz_table[r] == 0:
        return False
      else:
        magz_table[r] -= 1
    return True

時間複雜度:O(n + m)
空間複雜度:O(n + m)

優化可能性:

我們可以使用 Python 的 collections.Counter 來取代手動建構 hash table。

註:

  • Counter 是 collections 模組中的一個子類,用於計數可哈希對象(通常是字符或單詞)。
    功能:Counter 主要用於統計元素的頻率。它會為每個元素創建一個 dictionary 鍵,元素的計數作為 dictionary 的值。
    默認值:如果查詢一個不存在的鍵,Counter 會返回 0,而不是拋出 KeyError。
  • dict 是 Python 內置的 hash table,用於存儲任意的鍵值對。
    功能:dict 可以存儲任意類型的鍵值對,而不僅限於計數。
    默認值:如果查詢一個不存在的鍵,dict 會拋出 KeyError,除非使用 dict.get(key, default) 方法。
    靈活性:dict 更加通用,可以存儲各種類型的值,不僅限於計數。

另外,可以去掉 subset 檢查部分,因為這與構建 hash table 相比並不提供顯著的優勢,直接在遍歷 ransomNote 時做檢查即可。

from collections import Counter

class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    # 檢查字數是否足夠
    if len(ransomNote) > len(magazine):
      return False

    # 建立字母頻率表
    magz_counter = Counter(magazine)

    # 逐一檢查 ransomNote
    for char in ransomNote:
      if magz_counter[char] == 0:
        return False
      magz_counter[char] -= 1

    return True

時間複雜度:O(n + m)
空間複雜度:O(n)

Time and Space complexity analysis

Time

  1. 長度檢查和集合子集檢查:
    len(ransomNote) > len(magazine) 需要 O(1) 時間。
    set(ransomNote) 和 set(magazine) 的創建時間都是 O(n) 和 O(m),其中 n 是 ransomNote 的長度,m 是 magazine 的長度。
    set(ransomNote).issubset(set(magazine)) 的檢查時間是 O(n),因為子集檢查在最壞情況下需要遍歷 ransomNote 中的每個字符。
    綜上,這部分的時間複雜度是 O(n + m)。

  2. 構建 magz_table:
    遍歷 magazine 需要 O(m) 時間,每個字符的插入或更新操作在 hash table 中是 O(1) 時間。
    因此,這部分的時間複雜度是 O(m)。

  3. 檢查並更新 magz_table:

遍歷 ransomNote 需要 O(n) 時間,每個字符的查找和更新操作在 hash table 中是 O(1) 時間。
因此,這部分的時間複雜度是 O(n)。

綜合來看,總的時間複雜度是 O(n + m)。

Space

  1. 集合創建:

set(ransomNote) 和 set(magazine) 各自需要 O(n) 和 O(m) 的空間。
hash table magz_table 最多包含 magazine 中所有不同字符的數量,最壞情況下需要 O(m) 的空間。
如果另外用 counter 創建 ransom_note_count 的 hash table 最壞情況下需要 O(n) 的空間。

綜合來看,總的空間複雜度是 O(n + m)。

卡住的地方

在寫程式的時候,我卡在了一個小細節:

print(set(ransomNote)) # Output: {'a'}
print(set(magazine))  # Output: {'a', 'b'}
print(set(ransomNote) not in set(magazine)) # Output: True

我原本以為 set(ransomNote) not in set(magazine) 可以判斷 ransomNote 的字母是不是 magazine 的子集,但
後來我才發現,not in 因為它的意思是檢查 set(ransomNote) 是否作為一個整體元素存在於 set(magazine) 中,而不是判斷一個集合是不是另一個集合的子集。正確的做法應該是使用 issubset()

Example

假設 ransomNote"aa"magazine"aab"

  • set(ransomNote){'a'}
  • set(magazine){'a', 'b'}

使用 issubset 方法:

set(ransomNote).issubset(set(magazine)) # True

使用 not in 方法:

set(ransomNote) not in set(magazine) # True

前者是正確的,因為它檢查 'a' 是否在 {'a', 'b'} 中。而後者是不正確的,因為 {'a'} 不是 {'a', 'b'} 的一個元素。

Lesson learn

這題幫我

  1. 加強創建 hash table 的用法(Python 的 set 和 dict 都是基於 hash table 實現的)
  • set:用來存儲不重複的元素,主要用於檢查唯一性和集合操作(如聯集、交集和差集)。
  • dict:用來存儲鍵值對(key-value pairs),主要用於快速查找、插入和刪除鍵值對。
  1. set, dict, collect 的語法熟悉度

列出幾個適合使用 hash table 的情況:

  1. 頻率計數:

當需要計算元素出現的次數時,例如字符、單詞、或數字的頻率。
例子:統計字符串中每個字符的出現次數,檢查兩個字符串是否為字母異位詞(Anagram)。

  1. 快速查找:

當需要快速查找某個元素是否存在時。
例子:從一個列表中快速查找某個值,或在 dictionary 中查找某個鍵是否存在。

  1. 唯一性檢查:

當需要檢查元素是否唯一時。
例子:檢查一個字符串中的字符是否全都唯一,檢查一組數字中是否有重複值。

  1. 配對與對應:

當需要建立一對一對應或一對多對應的關係時。
例子:將每個單詞映射到其定義,或將學生 ID 映射到學生信息。

  1. 累積求和或其他操作:

當需要累積計算某些數據時,例如求和、計算最大值或最小值。
例子:累積計算不同產品的銷售額,統計每個類別的商品數量。


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言